//
//  340. 至多包含 K 个不同字符的最长子串.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/2/6.
//

import Foundation

//https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/
//给你一个字符串 s 和一个整数 k ，请你找出 至多 包含 k 个 不同 字符的最长子串，并返回该子串的长度。
//
//
//
//示例 1：
//
//输入：s = "eceba", k = 2
//输出：3
//解释：满足题目要求的子串是 "ece" ，长度为 3 。
//示例 2：
//
//输入：s = "aa", k = 1
//输出：2
//解释：满足题目要求的子串是 "aa" ，长度为 2 。
//
//
//提示：
//
//1 <= s.length <= 5 * 104
//0 <= k <= 50

func 至多包含K个不同字符的最长子串(_ s: String, _ k: Int) -> Int {
    let chars = [Character](s)
    var left = 0
    var ans = 0
    var map: [Character: Int] = [:]
    for index in 0..<chars.count {
        let count = map[chars[index]] ?? 0
        map[chars[index]] = count + 1
        while map.count > k {
            let removeKey = chars[left]
            if let removeValue = map[removeKey] {
                if removeValue > 1 {
                    map[removeKey] = removeValue - 1
                } else {
                    map.removeValue(forKey: removeKey)
                }
            }
            left += 1
        }
        ans = max(ans, index - left + 1)
    }
    return ans
}
